package de.fuberlin.inf.alp3.ue07;

import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.NoSuchElementException;
import java.util.Set;

public class TreeSet<T extends Comparable<T>> implements Set<T> {
    protected class Node {
        T value;
        Node left, right, parent;
        Node (T v) { value = v; }
    }
    protected Node root = null;

    @Override
    public boolean add(T value) {
        if (value == null) throw new NullPointerException();
        Node n = new Node(value);
        if (root == null) { root = n; return true; }
        Node curr = root;
        while (true) {
            int compare = curr.value.compareTo(value);
            if (compare == 0) return false;
            if (compare < 0)
                if (curr.right == null) { 
                    n.parent = curr;
                    curr.right = n;
                    return true;
                }
                else curr = curr.right;
            else
                if (curr.left == null) {
                    n.parent = curr;
                    curr.left = n;
                    return true;
                }
                else { curr = curr.left; }
        }
    }

    private Node getMinimum(Node n) {
        while (n.left != null) n = n.left;
        return n;
    }

    @Override
    public Iterator<T> iterator() {
        // TODO exercise 7 problem 1 a (5 credits)
        return new Iterator<T>() {
            Node current = getMinimum(root);
            public boolean hasNext() { return current != null; }
            public T next() throws NoSuchElementException {
                if (current == null ) throw new NoSuchElementException();
                T x = current.value;
                if (current.right == null) {
                    while ((current != root) && (current == current.parent.right))
                        current = current.parent;
                    if (current == root)
                        current = null; // no more elements
                    else
                        current = current.parent;
                }
                else current = getMinimum(current.right);
                return x;
            }
            public void remove() { throw new UnsupportedOperationException(); }
        };
    }

    public List<T> list(T from, T to) {
        // TODO exercise 7 problem 1 b (3 credits)
        // correct order not asked - so just go down till you reach borders
        List<T> list = new LinkedList<T>();
        addSubtree(list, this.root, from, to);
        return list;
    }

    private void addSubtree(List<T> list, Node n, T from, T to) {
        if (n == null) return;
        int compareFrom = n.value.compareTo(from);
        int compareTo = n.value.compareTo(to);
        if (compareFrom > 0) // n > from
            addSubtree(list, n.left, from, to);
        if (compareTo < 0) // n < to
            addSubtree(list, n.right, from, to);
        if ((compareFrom >= 0) && (compareTo <= 0))
            list.add(n.value);
    }

    @Override
    public boolean addAll(Collection<? extends T> arg0) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public void clear() {
        // TODO Auto-generated method stub
        
    }

    @Override
    public boolean contains(Object arg0) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean containsAll(Collection<?> arg0) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean isEmpty() {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean remove(Object arg0) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean removeAll(Collection<?> arg0) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public boolean retainAll(Collection<?> arg0) {
        // TODO Auto-generated method stub
        return false;
    }

    @Override
    public int size() {
        // TODO Auto-generated method stub
        return 0;
    }

    @Override
    public Object[] toArray() {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public <E> E[] toArray(E[] arg0) {
        // TODO Auto-generated method stub
        return null;
    }

}
